import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;





public class threeSum0 {
	public void tester()
	{
		int []a = {-5,1,-3,-1,-4,-2,4,-1,-1};
		List <List<Integer>> result =threeSum(a);
		Arrays.sort(a);
		System.out.println(a[0]);
	}
	
	public List<List<Integer>> threeSum(int[] num) {
        List <List<Integer>> result = new ArrayList <List<Integer>>();
        if(num.length < 1) return result;
        quicksort(num, 0, num.length -1);
        
        int count0 = 0, index1 = 0, index2 = 0;
        int pre = num[0];
        for(int i = 0 ; i < num.length ; i ++) {
            if(num[i] == 0) count0 ++;
            if(pre < 0 && num[i] >= 0) index1 = i-1; // the last negative number
            if(pre <= 0 && num[i] > 0) index2 = i; // the first positive number
            pre = num[i];
        }
        
        if(count0 >= 3) {
            List<Integer> t = new ArrayList <Integer>();
            t.add(0);
            t.add(0);
            t.add(0);
            result.add(t);
        }
        
        if(count0 >=1) {
            int a = 0, b = num.length -1;
            pre = 0;
            while(a <= index1 && b >= index2) {
                if(num[a] == pre) {
                    a++;
                }
                else if(-num[a] == num[b]) {
                    List<Integer> t = new ArrayList <Integer>();
                    t.add(num[a]);
                    t.add(0);
                    t.add(num[b]);
                    result.add(t);
                    
                    pre = num[a];
                    a++;
                    b--;
                }
                else if(-num[a] > num[b]) {
                    a++;
                }
                else if(-num[a] < num[b]) {
                    b--;
                }
            }
        }
        
        System.out.println(Arrays.toString(num));
        
        for(int i = 0 ; i < index1 ; i++) {
            if(i>0 && num[i] == num[i-1]) continue;
            int a = i+1, b = num.length -1;
            pre = 0;
            while(a <= index1 && b >= index2) {
            	System.out.println(num[i]+" "+num[a]+" "+num[b]);
                if(num[a] == pre) {
                    a++;
                }
                else if(-num[a]-num[i] == num[b]) {
                    List<Integer> t = new ArrayList <Integer>();
                    t.add(num[i]);
                    t.add(num[a]);
                    t.add(num[b]);
                    result.add(t);
                    
                    pre = num[a];
                    a++;
                    b--;
                }
                else if(-num[a]-num[i] > num[b]) {
                    a++;
                }
                else if(-num[a]-num[i] < num[b]) {
                    b--;
                }
            }
        }
        
        
        
        for(int j = index2; j < num.length-1 ; j++)
        {
            if(j>index2 && num[j] == num[j-1]) continue;
            int a = 0, b = num.length -1;
            pre = 0;
            while(a <= index1 && b > j) {
                if(num[a] == pre) {
                    a++;
                }
                else if(-num[a]-num[j] == num[b]) {
                    List<Integer> t = new ArrayList <Integer>();
                    t.add(num[a]);
                    t.add(num[j]);
                    t.add(num[b]);
                    result.add(t);
                    
                    pre = num[a];
                    a++;
                    b--;
                }
                else if(-num[a]-num[j] > num[b]) {
                    a++;
                }
                else if(-num[a]-num[j] < num[b]) {
                    b--;
                }
            }
        }
        
        return result;
    }
    
    public List <List<Integer>> add(List <List<Integer>> result, int a, int b, int c) {
        List<Integer> t = new ArrayList <Integer>();
        t.add(a);
        t.add(b);
        t.add(c);
        result.add(t);
        return result;
    }
    
    public int bs(int[] a, int s, int t) {
        int lo = s;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (t < a[mid]) hi = mid - 1;
            else if (t > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }
    
    public void quicksort(int [] list, int start, int end) 
	{
	    if(start > end) return;
		int pivot = list[(start + end) / 2];
		int a = start ;
		int b = end ;
		int temp = 0 ;
		
		while(a <= b)
		{
			while(list[a] < pivot)
				a++ ;
			while(list[b] > pivot)
				b-- ;
			if(a <= b)
			{
				temp = list[a] ;
				list[a] = list[b] ;
				list[b] = temp ;
				a++ ;
				b-- ;
			}
		}
		if(start < a-1)
			quicksort(list, start, a-1 ) ;
		if(a < end)
			quicksort(list, a, end ) ;
	}
}